#ifndef UHM_DISCRETE_BASE_TREE_HXX_
#define UHM_DISCRETE_BASE_TREE_HXX_

namespace uhm {

  // Data_ is type of data
  // N is capacity for children storage
  template<class Data_, Int_ N>
  class Tree_ : public Disp_ {
  public:

    typedef Data_ _Data_;

    class Tnd_ : public Disp_ {
    private:
      Int_      _id, _n_children;
      Tnd_*     _parent;
      Tnd_*     _children[N];
      Int_      _gen;
      Data_     _data;
    
    public:

      Tnd_() : _id(0), 
               _n_children(0),
               _parent(NULL), 
               _gen(0) { }

      Tnd_(Int_ id) : _id(id),
                      _n_children(0),
                      _parent(NULL),
                      _gen(0) { }
      
      Tnd_(Int_ id, Data_ data) : _id(id),
                               _n_children(0),
                               _parent(NULL),
                               _data(data),
                               _gen(0) { }
      
      Tnd_(const Tnd_ &b) : _id(b._id),
                            _n_children(b._n_children),
                            _parent(b._parent), 
                            _data(b._data),
                            _gen(b._gen) { 
        for (Int_ i=0;i<_n_children;++i)
          _children[i] = b._children[i];
      }
      virtual~Tnd_() { }
      
      void set_id(Int_ id) { _id = id; }
      Int_ get_id() const { return _id; }
      
      void set_data(Data_ data) { _data = data; }
      Data_ get_data() const { return _data; }
      
      void set_parent(Tnd_* parent) { _parent = parent; }
      Tnd_* get_parent() const { return _parent; }

      Int_ get_n_children() const{ return _n_children; }      
      void add_child(Tnd_* child) {
        UHM_ERROR(_n_children < N, UHM_ERROR_TREE_CHILD_INDEX);
        _children[_n_children++] = child;
      }
      Tnd_* get_child(Int_ i) const { 
        UHM_ERROR(i<N, UHM_ERROR_TREE_CHILD_INDEX);
        return _children[i]; 
      }

      Bool_ is_leaf() const { return (!get_n_children()); }
      Bool_ is_parent_null() const { return (_parent == NULL); }

      void set_gen() {
        _gen = 0;
        if (is_leaf()) {
          _gen = 0;
        } else {
          for (Int_ i=0;i<get_n_children();++i)
            _gen = max( _gen, _children[i]->get_gen() );
          ++_gen;
        }
      }
      void set_gen_recursive() {
        for (Int_ i=0;i<this->get_n_children();++i)
          _children[i]->set_gen_recursive();
        this->set_gen();
      }
      Int_ get_gen() const { return _gen; }

      virtual std::ostream& content(std::ostream& os) const  {
        if (!is_parent_null())
          os << "   Parent " << (this->get_parent()->get_id());
        else 
          os << "No Parent ";
        
        os << ", Me " << this->get_id() << ", Gen " << this->get_gen() ;
        
        if (get_n_children()) {
          os << ", Children("   << get_n_children() << ") ";
          for (Int_ i=0;i<get_n_children();++i)
            os << this->get_child(i)->get_id() << " ";
        }
        return (os << std::endl);
      }

      virtual std::ostream& content_recursive(std::ostream& os) const  {
        for (Int_ i=0;i<get_n_children();++i) {
          get_child(i)->content_recursive(os);
        }
        return content(os);
      }
    };

  private:
    // use fixed size
    Int_ _size;
    Tnd_* _root;

  protected:
    std::vector<Tnd_> _nds;

    // gen, location in nds
    std::vector< std::pair<Int_,Int_> > _sorted;

  public:

    Tree_() : _size(0), 
              _root(NULL)  { }
    Tree_(Tnd_* root) : _size(0), 
                        _root(root) { }
    Tree_(const Tree_ &b) : _size(b._size),
                            _root(b._root) {
      _nds.clear();
      _nds.reserve(b._size);
      for (Int_ i=0;i<b._nds.size();++i)
        _nds[i] = b._nds[i];
    }
    virtual~Tree_() { }

    void clear() { _size = 0; _root = NULL; _nds.clear(); _sorted.clear(); }

    Int_ get_size() const { return _nds.size(); }

    void reserve(Int_ size) { _nds.reserve(size); _size = size; }

    Tnd_* add_node(Data_ data) {
      Tnd_* r_val = NULL;
#pragma omp critical
      {
        // Do not allow push back beyond the size
        // Sometimes memory corruption happen
        UHM_ERROR(_size > _nds.size(), UHM_ERROR_TREE_NODE_INDEX);
        Int_ id = _nds.size();
        _nds.push_back(Tnd_(id, data));
        r_val = &_nds[id];
      }
      return r_val;
    }

    Int_ get_n_nodes() const { return _nds.size(); }

    void set_root(Tnd_* root) { 
      UHM_ERROR(root != NULL, UHM_ERROR_TREE_ROOT_NULL);
      _root = root; 
    }
    Tnd_* get_root() const { 
      //UHM_ERROR(_root != NULL, UHM_ERROR_TREE_ROOT_NULL);
      return _root; 
    }

    void set_gen() { 
      UHM_ERROR(_root != NULL, UHM_ERROR_TREE_ROOT_NULL);
      _root->set_gen_recursive(); 
    }

    void sort() {
      _sorted.clear();
      _sorted.reserve(_nds.size());
      for (Int_ i=0;i<_nds.size();++i)
        _sorted.push_back(std::make_pair(_nds[i].get_gen(),i));
      std::sort(_sorted.begin(), _sorted.end());
    }

    Int_ is_sorted() const { return _sorted.size(); }
    Tnd_* get_tnd_from_sorted(Int_ i) const {
      UHM_ERROR(is_sorted(), UHM_ERROR_TREE_NOT_SORTED);
      Tnd_* r_val = (Tnd_*)&(_nds[_sorted[i].second]);
      return r_val;
    }

    void get_tnds_from_sorted(Int_ level, std::vector<Tnd_*> &tnds) {
      UHM_ERROR(is_sorted(), UHM_ERROR_TREE_NOT_SORTED);
      tnds.clear();

      if (_root->get_gen() <= level) {
        tnds.reserve(1);
        tnds.push_back(_root);
      } else {
        tnds.reserve(_size);
        
        Int_ i=0,flag = false;
        for ( ;i<_nds.size();++i)
          if (_sorted[i].first == level) 
            break;
        
        for ( ;i<_nds.size();++i)
          if (_sorted[i].first == level)
            tnds.push_back((Tnd_*)&(_nds[_sorted[i].second]));
          else
            break;
      }
    }

    virtual std::ostream& content(std::ostream& os) const  {
      this->Disp_::content(os);
      os << "- Tree -  # Nodes " << this->get_n_nodes() << std::endl;

      for (Int_ i=0;i<_sorted.size();++i)
        os << "("<< _sorted[i].first << "," << _sorted[i].second << ") " ;
      os << std::endl;

      if (this->_root == NULL) {
        os << "Root is NULL\n";
        if (is_sorted()) 
          for (Int_ i=0;i<_nds.size();++i)
            _nds[_sorted[i].second].content(os) << std::endl;
        else
          for (Int_ i=0;i<_nds.size();++i)
            _nds[i].content(os) << std::endl;

      } else {
        os << "Post Order Traversal\n";
        _root->content_recursive(os);
      }
      return os;
    }
  };

}


#endif
